11297. Веселая функция – 2

Вычислить значение функции

Вход. Два целых числа x, y (0 ≤ x, y ≤ 25).

Выход. Вывести значение функции f(x, y).

Пример входа	Пример выхода
2 3	17

РЕШЕНИЕ

рекурсия

Анализ алгоритма

Реализуем рекурсивную функцию с запоминанием результатов.

Реализация алгоритма

Объявим двумерный массив для запоминания значений функции: dp[x][y] = f(x, y).

long long dp[26][26];

Реализация рекурсивной функции с запоминанием.

long long f(int x, int y)

{

if (x <= 0 || y <= 0) return 1;

if (dp[x][y] != -1) return dp[x][y];

if (x <= y) return dp[x][y] = f(x - 1, y) + f(x, y - 1) + 1;

return dp[x][y] = f(x, y / 2) + 2;

}

Основная часть программы. Читаем входные данные. Инициализируем ячейки массива dp значением -1. Вызываем функцию f(x, y) и выводим ее значение.

scanf("%d %d",&x,&y);

memset(dp,-1,sizeof(dp));

printf("%lld\n",f(x,y));